{% extends 'c-word.html' %} {% block title %} data | structure {% endblock title %} {% block point1 %}

structure - data

诞生本无数据结构概念

问题描述 -- 问题分析 -- 算法 -- 代码实现

data structure


definition

data

数据(data)是事实或观察的结果，是对客观事物的逻辑归纳，是用于表示客观事物的未经加工的的原始素材。
数据可以是连续的值，比如声音、图像，称为模拟数据。也可以是离散的，如符号、文字，称为数字数据。
在计算机系统中，数据以二进制信息单元 0,1 的形式表示。

structure

结构是指在一个系统或者材料之中，互相关联的元素的排列、组织。

data structure

数据结构是指在一个系统或者材料之中，相互关联的数据的排列、组织。

数据与数据之间的关系

从关联的角度来说，数据与数据之间的关系：一对一，一对多，多对多，无关

B - 计算机系统下的数据结构

以下所涉及的数据结构概念特指在计算机系统下的数据结构。

course frame

定义

在计算机系统中，相互关联的数据的排列、组织。（数据来源于对现实生活的抽象，用二进制表示）

计算机系统只能识别二进制格式的数据。

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

B = (D, R)


B = (D, R, O)

研究内容

在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
“数据结构”作为一门独立的课程在国外是从1968年才开始设立的。 1968年美国唐纳德·克努特（Donald Ervin Knuth）教授开创了数据结构的最初体系，他所著的《计算机程序设计艺术》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”在计算机科学中是一门综合性的专业基础课，数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。
计算机科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示，信息的处理 。
而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。数据的结构，直接影响算法的选择和效率。
计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。
寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。当人们用计算机处理数值计算问题时，所用的数学模型是用数学方程描述。所涉及的运算对象一般是简单的整形、实型和逻辑型数据，因此程序设计者的主要精力集中于程序设计技巧上，而不是数据的存储和组织上。然而，计算机应用的更多领域是“非数值型计算问题”，它们的数学模型无法用数学方程描述，而是用数据结构描述，解决此类问题的关键是设计出合适的数据结构，描述非数值型问题的数学模型是用线性表、树、图等结构来描述的。
计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。
数据是信息的载体，是可以被计算机识别存储并加工处理的描述客观事物的信息符号的总称。所有能被输入计算机中，且能被计算机处理的符号的集合，它是计算机程序加工处理的对象。客观事物包括数值、字符、声音、图形、图像等，它们本身并不是数据，只有通过编码变成能被计算机识别、存储和处理的符号形式后才是数据。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体考虑。一个数据元素由若干个数据项组成。数据项是数据结构中讨论的最小单位。有两类数据元素：若数据元素可再分，则每一个独立的处理单元就是数据项，数据元素是数据项的集合；若数据元素不可再分，则数据元素和数据项是同一概念，如：整数"5"，字符 "N" 等。例如描述一个学生的信息的数据元素可由下列6个数据项组成。其中的出生日期又可以由三个数据项："年"、"月"和"日"组成，则称"出生日期"为组合项，而其它不可分割的数据项为原子项。
关键字指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 "主" 关键字，否则称之为 "次" 关键字。
数据对象是性质相同的数据元素的集合，是数据的一个子集。数据对象可以是有限的，也可以是无限的。
数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。在早期，计算机主要用于科学和工程计算，进入八十年代以后，计算机主要用于数据处理。据有关统计资料表明，计算机用于数据处理的时间比例达到80%以上，随着时间的推移和计算机应用的进一步普及，计算机用于数据处理的时间比例必将进一步增大。

研究对象

数据的逻辑结构

数据的逻辑结构是从具体问题抽象出来的数学模型，反映数据元素之间的逻辑关系，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关；是描述数据元素及其关系的数学特性的，有时就把逻辑结构简称为数据结构。
逻辑结构是在计算机存储中的映像，形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。
数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储结构是一种顺序存取的存储结构，线性表的链式存储结构是一种随机存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。
根据数据元素间关系的不同特性，通常有下列四类基本的逻辑结构：

| 集合结构

数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；

| 线性结构

数据结构中的元素存在一对一的相互关系；

线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。在实际问题中线性表的例子是很多的，如学生情况信息表是一个线性表：表中数据元素的类型为学生类型; 一个字符串也是一个线性表：表中数据元素的类型为字符型，等等。
线性表是最简单、最基本、也是最常用的一种线性结构。 线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，通常记为： (a1，a2，… ai-1，ai，ai+1，…an) ，其中n为表长， n=0 时称为空表。 它有两种存储方法：顺序存储和链式存储，它的主要基本操作是插入、删除和检索等。

| 树形结构

数据结构中的元素存在一对多的相互关系；

| 图形结构

数据结构中的元素存在多对多的相互关系，也称网状结构。

数据的物理结构


指数据的逻辑结构在计算机存储空间的存放形式。 
数据的物理结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成一种或多种存储结构。
数据元素的机内表示（映像方法）： 用二进制位（bit）的位串表示数据元素。通常称这种位串为节点（node）。当数据元素有若干个数据项组成时，位串中与各数据项对应的子位串称为数据域（data field）。因此，节点是数据元素的机内表示（或机内映像）。
关系的机内表示（映像方法）：数据元素之间的关系的机内表示可以分为顺序映像和非顺序映像，常用两种存储结构：顺序存储结构和链式存储结构。顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像借助指示元素存储位置的指针来表示数据元素之间的逻辑关系。

顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。
链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现
索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。

数据结构的运算

意义

一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率。
在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。
选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。

为什么要学习“数据结构”

为了便于对数据进行操作以及算法的优化。








数据结构和算法

算法的设计与实现

算法的设计取决于数据（逻辑）结构，而算法的实现依赖于采用的存储结构。数据的存储结构实质上是它的逻辑结构在计算机存储器中的实现，为了全面的反映一个数据的逻辑结构，它在存储器中的映象包括两方面内容，即数据元素之间的信息和数据元素之间的关系。不同数据结构有其相应的若干运算。数据的运算是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新和排序等。
数据的运算是数据结构的一个重要方面，讨论任一种数据结构时都离不开对该结构上的数据运算及其实现算法的讨论。
数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。

数据类型

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。数据类型可分为两类：原子类型、结构类型。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。
计算机中表示数据的最小单位是二进制数的一位，叫做位。我们用一个由若干位组合起来形成的一个位串表示一个数据元素，通常称这个位串为元素或结点。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。元素或结点可看成是数据元素在计算机中的映象。
一个软件系统框架应建立在数据之上，而不是建立在操作之上。一个含抽象数据类型的软件模块应包含定义、表示、实现三个部分。

不同的数据结构其操作集不同

对每一个数据结构而言，必定存在与它密切相关的一组操作。若操作的种类和数目不同，即使逻辑结构相同，数据结构能起的作用也不同。
不同的数据结构其操作集不同，但下列操作必不可缺：

1,结构的生成；
2.结构的销毁；
3,在结构中查找满足规定条件的数据元素；
4,在结构中插入新的数据元素；
5,删除结构中已经存在的数据元素；
6,遍历。

抽象数据类型

抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。抽象数据类型可用以下三元组表示：（D，S，P）。D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT的定义为：

        ADT 抽象数据类型名：{ 数据对象：（数据元素集合），数据关系：（数据关系二元组结合），基本操作：（操作函数的罗列）}；

| 两个重要特性

抽象数据类型有两个重要特性：

数据抽象
用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。
数据封装
将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。

构成

数据结点

数据结点（数据元素），简称结点（node）：
描述一个独立事物的名称、数量、特征、性质的一组相关信息组成一个数据结点；
通常，一个节点含有多个数据项（data item）
  • 结点的类型：结构型
  • 关键字（key）
单值类型的结点：只含一个数据项

数据结点间的关系集

数据结点间的运算集



种类




表 - 一对一

树 - 一对多

图 - 多对多

散 - 无关


B | D

数据集合

B | R

数据间的关系集合

一对一（表）：
一对多（树）：层次关系、分支关系、嵌套关系
多对多（图）：
无关（散）：

B | O

数据的操作集合 


前三项为基本运算，后六项都可以通过前三项的组合实现。

查找


数据结构的抽象和实现

数据的逻辑结构（logical form）

B = (D, R)

B = (D, R, O)

逻辑结构示例



数据的物理结构（physical form）




表结构

线性表（顺序表、链表、栈（顺序栈、链栈）、队（顺序队、链队））
散列表

线性表（linear list）

准确地描述表的定义
知道表的存储结构特征
掌握顺序表的描述方式


| 逻辑实现

线性表 | D

具有 n(n >= 0) 个数据结点（元素）的序列 A = (a1, a2, ..., an)；数据集合可以为空。

线性表 | R

先后次序

首结点和尾结点
表的长度
空表
前驱和后继（左邻和右邻）
有序表

线性表 | O


| 物理实现



线性表采用顺序存储的方式存储就称之为顺序表。
顺序表是在计算机内存中以数组的形式保存的线性表。 顺序表是指用一组地址连续的存储单元依次存储数据元素的线性结构。

线性表采用指针链接的方式存储就称之为链表。 线性表是从逻辑结构的角度来说的，除了头和尾之外，它的每一个元素都只有一个前驱元素和一个后驱元素。

各种队列（单向、双向、循环队列），栈等都是线性表的不同例子。
而数组是从物理存贮的角度来说的，线性表可以用数组存贮也可以用链表来存贮。同样的队列和栈也可以用数组和链表存贮，各有利弊。具体使用时，根据具体情况选择。

顺序存储 - 顺序表（sequential list）

存储结点的逻辑次序与物理次序一致。



链式存储 - 链表（linked list）

存储结点的逻辑次序与物理次序不一致

顺序表和链表的优缺点及适用场合

顺序表：（1）优点：查找速度较快，查找方便                （2）缺点：动态操作困难                （3）适用于查找操作 链表：（1）优点：动态操作方便，方便扩展            （2）缺点：查询效率低，不利于查询            （3）适用于动态的删除， 插入等操作

顺序表：内存中地址连续

             长度不可变更

             支持随机查找 可以在O(1)内查找元素

             适用于需要大量访问元素的 而少量增添/删除元素的程序

 链表 ：内存中地址非连续

            长度可以实时变化

            不支持随机查找 查找元素时间复杂度O（n）

           适用于需要进行大量增添/删除元素操作 而对访问元素无要求的程序

| 顺序表 - 类似数组

O | 查找

















| 二分查找算法











O | 插入




O | 删除




| 链表

准确地描述表的链式存储结构
写出单向链表的指定位置插入和删除的程序段
知道链表的种类和作用
知道常用链表的特点和图示方法
能够写出单向加尾链表查找的算法
能够写出单向加头循环链表的删除算法
能够写出双向链表的插入和删除算法
能够写出构造有序链表的算法

定义

链表就是表头指针和一串相继链接的结点的总称。


特点

种类


链表的图示




单向链表结点结构的定义


结点的产生和回收










结点的链接操作



O | 查找

单向加尾链表的查找

O | 插入




O | 删除





单向加头循环链表的删除


构造有序链表








| 栈

能够准确描述栈的特点
能够写出顺序栈的入栈和出栈算法
能够写出链栈的入栈和出栈算法
能够准确描述栈在程序中断中的作用
掌握简单算术表达式求值的方法

定义

只允许在同一端点出进行插入或删除的表结构称为栈（stack），栈是一种后进先出结构，又称为后进先出表（LIFO 表）。


术语

栈顶（top）：允许插入和删除的一端，top 指针总是指向栈顶。
栈底（bottom）：不允许插入和删除的一端。
进栈（push，压栈）：元素插入栈的过程。
出栈（pop，退栈）：从栈中弹出一个元素的过程。
栈空
栈满
栈溢出

栈的特点

后进先出，LIFO

栈的实例

子弹夹
浏览器的类似后退和前进按钮
函数之间的嵌套调用以及递归函数的执行

栈的物理实现 

| 顺序栈

| 链栈

栈的应用

| 程序中断

中断：一个程序执行期间被其他程序所打断。
断点：被打断的地方。
现场（栈架）：被打断的程序当前的执行情况。

栈架与栈架之间服从后进先出的栈原则。
同一个栈架，数据存储的次序也遵守后进先出的栈原则。
保护现场和恢复现场。
嵌套中断的现场需要层层保护。








| 对列

能够准确描述队列的特点
能够写出顺序对的入队和出队算法

定义

允许在一端插入、另一端删除的表叫做队，或队列。

对结构好似一端两端开口的管道，结点从一端进入，从另一端退出。

对结构遵循先进先出原则，又称先进先出表（FIFO 表）。

术语

队尾（rear）：允许插入的一端
队头（front）：允许删除的一端
队满
队空
进队和出队：队的插入和删除

指针 first 和 last 分别指向队头和队尾，每当进队时移动尾指针，每当出队时移动首指针。


队的特点

先进先出（FIFO）

队的实例

排队买票

循环队（环形队 cyclic queue）

队的物理实现

| 顺序队

| 链式队

散列表

复述散列表的作用和意义
学会散列函数的设计方法
实现散列表的构造、插入和查找
选择并会使用开放地址法解决散列冲突

散列函数的设计原则


散列函数的设计方法


散列冲突






散列表的构造

树结构

什么是树
树的存储方法
能够准确复述树结构的相关术语
能够用图示和 C 语言描述树结构的存储方式
二叉树的基本概念和存储方法，区别不同的二叉树
能够用 C 语言描述二叉树的双链表的存储结构
能够准确图示森林、树、二叉树的相互转换


基本概念

定义

树是一种非线性的数据结构。

树是递归定义的，用来描述数据之间层次关系、分支关系和嵌套关系的基本数据结构。

术语



结点的度：当前结点所具有的子树的个数
树的元数：一棵树中，结点的度能允许的最大值
树叶：度数为 0 的结点（也称终端结点）
分枝点（内结点）：非叶结点
兄弟：同父的结点互为兄弟
结点的层数：根的层数定为 1；递推地，第 i 层结点的儿子层数为 i + 1
结点的高度：叶的高度定为 1；递推地，非叶结点的高度等于它各个儿子高度的最大值加 1
树高：等于其根结点的高度
有序树：树中结点的儿子按照某种次序排列
无序树：
位置树：一颗有序树中规定了每个结点儿子的位置
森林：树的集合，一个森林可包含 0 至多棵树

树的表示方法

 

计算机中树的存储方法

多重链接




儿子兄弟链




父亲链域



二叉树

定义

二叉树也称二分树，也称二元位置树：每个结点最多 2 个儿子，称为左、右儿子。

五种基本形态


二叉树的性质


二叉树的存储


| 静态存储 -- 顺序顺序法

补齐为完全二叉树，然后在按完全二叉树的存储方法存储

| 动态存储 -- 双链法






| 满二叉树




| 完全二叉树

完全二叉树是满二叉树的一部分；
满二叉树是完全二叉树的特例










| 非完全二叉树

补齐为完全二叉树，然后在按完全二叉树的存储方法存储


普通树与二叉树的相互转换

将复杂树的问题转换为简单二叉树的问题 -- 化繁为简

将树转换为二叉树





树中每个结点指向最左儿子的边不变


添加边，链接其紧挨着的第一个兄弟


去掉除链接的最左儿子的其余儿子的边，然后顺时针旋转 45度，即可得到二叉树

将二叉树转换为树

树转换为二叉树的逆过程

注意：
要转换为树的二叉树，其根结点没有右子树

森林与二叉树的转换

可以借助树与二叉树的转换来实现

森林转换为二叉树


二叉树转换为森林


二叉树的运算

查找 - 递归遍历



| 先根遍历


| 中根遍历


| 后根遍历


二叉树的构造

能够准确判断二叉树构造的唯一性条件
能够编程实现先（后）序、中序构造二叉树的递归算法
能够编程实现用扩充先序序列构造二叉树的递归算法


二叉树构造的问题











先（后）序序列、中序序列构造二叉树






扩充先（后）序序列唯一构造二叉树










二叉树 | 检索树

能够准确描述检索树的基本特征
能够编程实现检索树的查找、插入、构造、删除算法（递归、非递归）

什么是检索树


检索树的特点

左小右大
中序有序

检索树的查找

检索树的查询效率取决于树的高度






检索树的插入和构造

插入原则：简单、保中序



检索树的删除

原则：仅删除要删除的结点，并且保持中序有序

检索树的结点的三种情况：没有儿子，有一个儿子，有两个儿子







二叉树 | 检索树 | 平衡树

能够准确阐述平衡树的定义、性质
能够通过图示准确分析描述平衡树的插入、删除算法
能够准确图示给定平衡树的插入删除过程


二叉树 | 哈夫曼树

用于哈夫曼编码，无损压缩数据

什么是哈夫曼树

如何构造哈夫曼树

哈夫曼算法实现

哈夫曼编译和译码

应用实例


图结构

准确复述图的基本概念和相关术语
理解邻接矩阵的物理含义
准确掌握图的存储方法

定义 


术语

顶点的度

子图

路径

回路：起点和终点相重合的简单路径
无向回路（圈）
有向回路
无向图的连通性



无向边

有向边

加权边

图的种类


邻接矩阵






散结构

如何利用高级语言描述存储结构

 数组可以用来描述顺序存储

一个数组元素便是一个存储结点
下标作为结点的存储地址
































{% endblock point1 %}